Many methods have been developed in two-dimensional (2D) computer graphics in recent times to improve the quality of output. Various methods of rendering of graphical objects that have a solid color or a linear or radial blend between two colors are known. More recently methods such as Gouraud shaded triangle meshes and blends across parametric patches have been adapted from three-dimensional (3D) computer graphics to 2D computer graphics in order to greatly increase the shapes and styles of blends that may be produced.
A geometric object referred to herein as a “parametric patch” may be defined by four curves (e.g., Bézier curves) in x, y coordinate space. The four curves that typically maps a unit square in parametric u, v coordinate space. Examples of such parametric patches are Coons and tensor-product patches. A Coons patch may be defined by four connected Bézier Curves and four implicit control points. “Type 6” shading performed in accordance with the Portable Document Format (PDF) ISO32000-1:2008 specification type 6 shading comprises one or more colored Coons patches. A tensor-product patch may be defined by four connected Bézier Curves and by additional control points. Such type 6 shading will be referred to below as “PDF shading type 6”.
“Type 7” shading performed in accordance with the PDF ISO32000-1:2008 standard type 7 shading comprises one or more colored tensor-product patches. Such type 7 shading will be referred to below as “PDF shading type 7”. The Coons patch determined (PDF Type 6) as part of the PDF shading type 6 is a special case of a tensor-product patch. Coons patches may be converted to tensor-product patches. The PDF shadings are specified in the Portable Document Format (PDF) ISO32000-1:2008.
Each point in a PDF shading type 6 or type 7 patch may be associated with a t-value which is mapped to a color value using a PDF shading color function. The PDF shading color function may be non-linear. In PDF shading type 6 or type 7 shading, the color data of each of the four corners of the parametric patch may be specified by t-values.
Vector graphics on imaging devices, such as display devices or printers, are typically converted to raster graphics data in a process called rasterization. During rasterization, surfaces defined by geometric objects may be subdivided into polygons (e.g. triangles or quadrilaterals) in a process called tessellation. In particular, a surface of an object may be described as a parametric patch, in which a function of two variables (u, v) is used to describe patches of the surface in three dimensional (3D) space: (x, y, z)=(X(u, v), Y(u, v), Z(u, v)).
where X(u, v), Y(u, v) and Z(u, v), are functions in the parameters (u, v). Properties of the surface, such as textures or colours, may be applied to the surface in terms of either calculated positions, or equivalently, in terms of the parameters (u, v). As described above, examples of parametric patches include Coons patches, Bezier patches, and Tensor product patches. The boundary of such patches is defined as a set of four Bezier curves.
To render the surface, the surface is typically subdivided into triangles, over which the properties of the patch may be represented. The properties of the patch are represented using linear functions to provide a good approximation of the patch, defined by a tolerance. The tolerance is a quality parameter that is usually provided in a print job definition. This part of the rendering process is referred to as “tessellation”. Tessellation is performed because direct calculation of pixel values is computationally expensive.
Two or more patches may be joined together to form a mesh of patches. When patches are independently tessellated, the tessellated patches often do not match at the boundaries of the patches. For example, patches with a common boundary may not have the same number of triangle vertex points along the boundary curve, and the positions of the vertices may not correspond, because of differences in the local geometry on either side of the boundary. Such errors are referred to as crack artefacts, because the errors appear as cracks at the boundary between the patches.
Crack artefacts may be addressed by separately vectorising the boundary curves. The curves may be approximated by linear segments, such that the linear segments match the exact boundary curve to within a flatness tolerance, ε. The vertices of the polygon formed by the vectorised boundary curves are then used as vertices of the tessellation for the patch. The vectorising method ensures that the boundary curve is represented by the same set of points in the two patches for which the boundary curve forms the common boundary. However, the vectorising method restricts the points that may be used for performing a tessellation of the patch in the region near the boundary curve, so that it may not be possible to obtain an interior tessellation that fits the flatness tolerance criteria near the boundary curve.
A tighter flatness tolerance than originally defined in the print job definition may be used to address the problem created by restricting the points that may be used for performing a tessellation of the patch in the region near the boundary curve. This however leads to a proliferation of triangles which consequently increases rendering time due to the time to generate the triangles, and the time to render the triangles separately. Furthermore, this still does not guarantee that it is possible to obtain an interior tessellation that fits the flatness tolerance criteria near the boundary curve.
Thus, a need clearly exists for a crack-free tessellation that meets a given flatness tolerance criterion.